`
https://leetcode.cn/problems/sliding-puzzle/
`

/**
 * @param {number[][]} board
 * @return {number}
 */
var slidingPuzzle = function (board) {
  // 将二维扁平化
  let start = ''
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      start += board[i][j]
    }
  }

  // 最终结果
  const target = '123450'

  // bfs 队列
  let q = [start]

  // 已访问过的状态
  const visited = new Set()
  visited.add(start)

  // 步数
  let step = 0

  while (q.length !== 0) {
    // 固定长度
    const sz = q.length

    for (let i = 0; i < sz; i++) {
      const cur = q.shift()

      if (cur === target) return step

      // 将数字 0 和相邻的数字交换位置
      for (const neighbor of getNeighbors(cur)) {
        // 防止走回头路
        if (!visited.has(neighbor)) {
          q.push(neighbor);
          visited.add(neighbor);
        }
      }
    }
    step++
  }

  return -1
};

// 获取所有相邻状态
function getNeighbors(board) {
  // 记录一维字符串的相邻索引
  const mapping = [
    [1, 3],
    [0, 4, 2],
    [1, 5],
    [0, 4],
    [3, 1, 5],
    [4, 2],
  ];

  const idx = board.indexOf('0');
  const neighbors = [];
  for (const adj of mapping[idx]) {
    const newBoard = swap(board, idx, adj);
    neighbors.push(newBoard);
  }
  return neighbors;
}

// 交换 i 和 j 位置
function swap(board, i, j) {
  const chars = board.split('');
  [chars[i], chars[j]] = [chars[j], chars[i]];
  return chars.join('');
}